Due to the increasing need for rapid matching capabilities, in networking hardware equipment for example, content addressable memories (CAMs) continue to proliferate. A CAM may perform matching functions by applying a search key or “comparand” to a table of stored data values. A CAM may then determine if any of the data values match a given search key.
CAM devices may take a variety of forms. As but a few of the possible examples, some CAM devices are based on particular types of CAM cells. Such cells may include storage circuits integrated with compare circuits. Examples of storage circuits may be static random access memory (SRAM) type cells or dynamic RAM (DRAM) type cells. Alternate approaches may include RAM arrays, or the like, with separate matching circuits and/or matching processes executed by a processor, or the like.
Conventional CAM devices may include both binary and ternary CAM devices. Binary CAM devices can provide a bit-by-bit comparison between a stored data value and a search key. Ternary CAM devices can provide maskable compare operations that can selectively exclude predetermined bits of a data value from a compare operation.
Typically, a conventional CAM device can generate match indications for each entry. That is, each entry can be compared with an applied search key value. If a search key value matches a stored data value, a match (or “hit”) indication may be generated for the entry. Conversely, if a search key value does not match a stored data value, a mismatch (or “miss”) indication may be generated for the entry.
Match results in a CAM device may include single match results, that can be generated when a single entry matches an applied key value, as well as multiple match results, that may be generated when more than one entry matches an applied key value. Typically, a search result may include an index value, which can serve as an indirect pointer to associated data, or search result data itself (associated data). Thus, a search result may be conceptualized as including not only a result (an index or associated), but also a status (match, multiple match, no match, etc.).
Referring now to FIG. 11, a conventional CAM device is set forth in a block diagram and designated by the general reference character 1100. A conventional CAM device 1100 may include a number of entries (ENTRY0 to ENTRYn) 1102 and a priority encoder 1104. Each entry (ENTRY0 to ENTRYn) may store a data value for comparison with an applied key value KEY. In a conventional compare operation, a key value KEY can be applied to entries (ENTRY0 to ENTRYn) essentially simultaneously. That is, a key value KEY can be applied to all entries (ENTRY0 to ENTRYn).
Each entry (ENTRY0 to ENTRYn) can generate a corresponding match indication (MATCH0 to MATCHn) that can reflect whether or not data for an entry matches an applied key value. More a particularly, if entry data matches a key value, a corresponding match indication can be active. If entry data does not match a key value, a corresponding match indication can be inactive.
Priority from among multiple active match indications can be established by a priority encoder 1104. More particularly, a conventional priority encoder 1104 can prioritize match indications according to a “physical” priority of the entries. A physical priority can be a priority established by a physical location of an entry on a conventional CAM device. Typically, physical priority can correspond to an address of an entry, with a lower address value having priority over a higher address value.
In the example of FIG. 11, a priority encoder 1104 can encode a highest priority match indication into an index value INDEX. In some conventional approaches, an index value can be used to access associated data, or alternatively, a highest priority match indication can access associated data directly.
In the particular example of FIG. 11, a conventional priority encoder 1104 may also include a multiple match detect circuit that can generate status data. Status data can include a single match indication MATCH, multiple match indication MMATCH, and no match indication MISS.
In many applications, it is desirable to generate match results for as many entries as possible, as fast as possible. However, as CAM arrays are scaled upward, lines (e.g., match lines, bit lines, word lines, etc.) can get longer, requiring more power to drive to particular logic level. Further, such lines may present greater capacitive loads to driver circuits, which can slow operations.
One way to scale up compare results can be to employ multiple CAM devices. A conventional search engine system that can include multiple conventional CAM devices, such as that shown in FIG. 11, is shown in FIG. 12 and designated by the general reference character 1200. In the example of FIG. 12, a search engine system 1200 includes “n+1” CAM devices, shown as 1202-0 to 1202-n. A search engine system 1200 may perform search operations in response to commands from a requesting device. In FIG. 12, a requesting device is a network processing unit (NPU) 1204.
FIG. 12 shows an example of a bus based search engine system. In a bus based search engine system, CAM devices may be commonly connected to a requesting device and to one another by a common bus. Thus, in FIG. 12 CAM devices (1202-0 to 1202-n) can be commonly connected to each other and to an NPU 1204 by a bus 1206.
In conventional bus based search engine systems, each CAM device may simultaneously compare a key with entries of its respective CAM array. If a CAM device has a match, the CAM device may forward a match indication (e.g., a flag or the like) to a next, lower priority CAM device. A higher priority CAM device may output a result and a lower priority CAM device can be disabled from outputting data to the common output bus. If, however, a higher priority CAM device does not have a match, such a device may not assert a match indication, and a lower priority CAM device can provide an output result.
A drawback to an approach like that of FIG. 12 can be the lack of flexibility in entry arrangement, as well as the additional complexity of connection. Flexibility can be limited as priority is based on a CAM device position in the system. Connection complexity can be greater as connections can be needed that disable lower priority CAM devices in the event of a match in a higher priority CAM device.
In light of the above, it would be desirable to arrive at some way of generating compare results for a large number of CAM entries, without the drawbacks of conventional approaches.